package cn.cxq.learning.array;

/**
 * 链接：https://www.nowcoder.com/questionTerminal/269b4dbd74e540aabd3aa9438208ed8d?toCommentId=9182309
 * 来源：牛客网
 *
 * [编程题]不相邻最大子序列和
 * 热度指数：3879时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
 * 算法知识视频讲解
 * 给你一个n（1\leq n\leq10^51≤n≤10
 * 5
 *  ），和一个长度为n的数组，在不同时选位置相邻的两个数的基础上，求该序列的最大子序列和（挑选出的子序列可以为空）。
 * 示例1
 * 输入
 * 3,[1,2,3]
 * 输出
 * 4
 * 说明
 * 有[],[1],[2],[3],[1,3] 4种选取方式其中[1,3]选取最优，答案为4
 * 示例2
 * 输入
 * 4,[4,2,3,5]
 * 输出
 * 9
 * 说明
 * 其中[4,5]的选取方案是在满足不同时选取相邻位置的数的情况下是最优的答案
 *
 * 备注:
 * 输入的值在int范围内
 */
public class SubSequence {
    // 动态规划解决不相邻最大子序列和
    public long subsequence (int n, int[] array) {

        if (array.length == 0) {
            return 0;
        }

        if (array.length == 1) {
            return array[0];
        }

        int[] dp = new int[n];

        // 为遍历作初始化准备
        dp[0] = array[0];

        if (array[0] < array[1]) {
            dp[1] = array[1];
        } else {
            dp[1] = array[0];
        }

        // 思路： 如果第i项为负数，直接取前一项的值；
        // 如果前i-2项子序列大小 + array[i] 大于 前i-1项子序列大小 ，就取前者，否则就取后者
        // 最后dp数组最后一个元素就是最大值了
        for (int i = 2; i < array.length; i++) {
            if (array[i] < 0) {
                dp[i] = dp[i - 1];
            } else {
                dp[i] = Math.max(dp[i - 2] + array[i], dp[i - 1]);
            }
        }
        return dp[n - 1];
    }
}
